# https://leetcode-cn.com/problems/coin-change-2/
# 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
#
# 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
#
# 假设每一种面额的硬币有无限个。
#
# 题目数据保证结果符合 32 位带符号整数。
#
#
#
# 示例 1：
#
# 输入：amount = 5, coins = [1, 2, 5]
# 输出：4
# 解释：有四种方式可以凑成总金额：
# 5=5
# 5=2+2+1
# 5=2+1+1+1
# 5=1+1+1+1+1
#
# 示例 2：
#
# 输入：amount = 3, coins = [2]
# 输出：0
# 解释：只用面额 2 的硬币不能凑成总金额 3 。
# 示例 3：
#
# 输入：amount = 10, coins = [10]
# 输出：1
#
#
# 提示：
#
# 1 <= coins.length <= 300
# 1 <= coins[i] <= 5000
# coins 中的所有值 互不相同
# 0 <= amount <= 5000
#
# dp, 本题关键是避免重复问题, 通过排序来实现, 确保最后追加的总是大于前面的:
# ----
# - d[k][i]为前i+1个硬币表示k的方法数
# - d[0][0] = 1
# - for i in len(coins):  d[k][i] = sum([d[k-each][i] for each in coins if k-each >= 0]) + sum(d[k][i-1] | if i >= 1)
#   即: {x0c0+x1*c1+...x_i-1*c_i-1} + ci
#
# 优化: 空间可以节省, 因为k方向和i方向是独立的, 可以先遍历i方向的, 由于i到i+1是累加, 因此可以改为一维数组.
from typing import List


class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        coins.sort()
        d = [[0] * len(coins) for _ in range(amount + 1)]
        for i in range(len(coins)):
            for k in range(0, amount + 1):
                if not k:
                    d[k][i] = 1
                    continue
                if i >= 1:
                    d[k][i] += d[k][i - 1]
                if k >= coins[i]:
                    d[k][i] += d[k - coins[i]][i]
        return d[amount][len(coins) - 1]


solution = Solution()
assert solution.change(5, [1, 2, 5]) == 4
assert solution.change(3, [2]) == 0
assert solution.change(5, [5]) == 1
